In computer operating systems, demand paging (as opposed to anticipatory paging) is a method of virtual memory management. In a system that uses demand paging, the operating system copies a disk page into physical memory only if an executing processes makes an attempt to access the page and that page is not already in memory (i.e., if a page fault/miss occurs). Pages demanded by the process are retrieved from secondary storage and loaded to main memory. By loading pages that are demanded by the executing process, less loading latency occurs at program startup, as less information is accessed from secondary storage and less information is brought into main memory. Further, as main memory is expensive compared to secondary memory, this technique reduces the amount of main memory needed, reducing the component costs of smart phones for example.
Pages stored in the secondary memory may be of a certain size, and requesting a page from the secondary memory means transmitting the page of the certain size to the main memory. This transfer requires the use of resources, such as data bus bandwidth and power. To reduce the use of such resources, pages comprising an entire compression block may be compressed prior to being copied to the main memory. The compression reduces the size of the page, thus reducing the resources required to load the compressed page to memory.
However, the decompression time of each page received at the main memory creates a performance bottleneck. Pages may be received by the main memory faster than the pages can be decompressed and the instructions or data in the page can be used. Some of the decompression work is done for pages containing code or data that won't be used, further delaying the use of the other instructions and data.
Further, efficient compression algorithms often employ lookbacks, which allow for patterns of previously compressed data to be used to more efficiently compress and decompress remaining data. However, compression algorithms independently compress blocks of data. As the block size gets smaller, there are fewer lookback opportunities and hence the compression ratio degrades.